#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

int rowHash[10];
int colHash[10];
int Hash[10];

pair<int, int> findNext( vector<vector<int> > &board)
{
	pair<int, int> ans;
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++)
			if (board[i][j] == 0) return make_pair(i, j);
	}
	return make_pair(-1,-1);
}

bool pass(pair<int, int> point, int val)
{
	int x = point.first;
	int y = point.second;
	int index = (x/3)*3 + y/3;
	int mask = 1 << val;

	if (rowHash[x] & mask || colHash[y] & mask || Hash[index] & mask) return false;
	return true;
}

bool solve( vector<vector<int> > &board, vector<vector<char> > &board1)
{
	pair<int, int> point = findNext(board);
	if (point.first == -1) {
		return true;
	}

	for (int i = 1; i <= 9; i++) {
		if(pass(point, i)) {
			int x = point.first;
			int y = point.second;
			int index = (x/3)*3 + y/3;
			board[x][y] = i;
			rowHash[x] |= 1 << i;
			colHash[y] |= 1 <<i;
			Hash[index] |= 1 << i;
			board1[x][y] = '0'+i;
			if (solve(board, board1)) return true;
			rowHash[x] ^= 1 <<i;
			colHash[y] ^= 1 << i;
			Hash[index] ^= 1 << i;

			board[x][y] = 0;
		}
	}
	return false;
}


class Solution {
    public:
        void solveSudoku(vector<vector<char> > &board1) {
            vector<vector<int> > board(9, vector<int>(9,0));

			for (int i = 0; i < 10; i++) {
				rowHash[i] = 0;
				colHash[i] = 0;
				Hash[i] = 0;

			}

            for (int i = 0; i < board1.size(); i++) {
                for (int j = 0; j < board1.size(); j++) {
                    if (board1[i][j] == ' ') board[i][j] = 0;
                    else board[i][j] = board1[i][j] - '0';
                }
            }

            for (int i = 0; i < board.size(); i++) {
                for (int j = 0; j < board.size(); j++) {
					if (board[i][j] == 0) continue;
                    rowHash[i] |= 1 << board[i][j];
                    colHash[j] |= 1 << board[i][j];
					int x = i/3;
					int y = j/3;
					int index = 3*x+y;
					Hash[index] |= 1 << board[i][j];
                }
            }


            solve(board, board1);

        }
};

vector<char> trans(const string &str)
{
    vector<char> ans;
    for (int i = 0; i < str.size(); i++) {
        ans.push_back(str[i]);
    }
    return ans;
}

//test in 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;

    cout << "-----------------Test 1--------------------" << endl;
    vector<vector<char> > input(9);
    input[0] = trans("53  7    ");
    input[1] = trans("6  195   ");
    input[2] = trans(" 98    6 ");
    input[3] = trans("8   6   3");
    input[4] = trans("4  8 3  1");
    input[5] = trans("7   2   6");
    input[6] = trans(" 6    28 ");
    input[7] = trans("   419  5");
    input[8] = trans("    8  79");
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++){
            cout << input[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    mySolution.solveSudoku(input);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++){
            cout << input[i][j] << " ";
        }
        cout << endl;
    }
    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
